Longest Valid Parentheses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/longest-valid-parentheses/

题目：
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()",
which has length = 4.

代码：

 class Solution {  
 public:  
   int longestValidParentheses(string s) {  
     stack<int> lefts;  
     int maxlen = 0, last = -1; // last index: 保存的是  
     for (int i = 0; i < s.size(); i++){  
       if (s[i] == '(') {  
         lefts.push(i);  
       } else {  
         if (lefts.empty())  
           last = i;  
         else {  
           lefts.pop();  
           if (lefts.empty())  
             maxlen = max(maxlen, i-last);  
           else  
             maxlen = max(maxlen, i-lefts.top());  
         }    
       }  
     }  
     return maxlen;  
   }  
 };  

155 Min Stack

来源：Leetcode

原帖：https://oj.leetcode.com/problems/min-stack/

题目：
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

代码：

 class MinStack {  
 public:  
   void push(int x) {  
     s.push(x);  
     if (min.empty()) {  
       min.push(x);  
     } else if (x <= min.top()) {  
       min.push(x);  
     }  
   }  
   
   void pop() {  
     if (s.empty()) {  
       cerr << "stack is empty" << endl;  
     }  
     if (s.top() == min.top()) {  
       min.pop();  
     }  
     s.pop();  
   }  
   
   int top() {  
     return s.top();  
   }  
   
   int getMin() {  
     assert(!min.empty());  
     return min.top();  
   }  
 private:  
   stack<int> s;  
   stack<int> min;  
 };  

Maximal Rectangle

来源：Leetcode

原帖：http://oj.leetcode.com/problems/maximal-rectangle/

题目：
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

代码：

 class Solution {  
 public:    
   int maximalRectangle(vector<vector<char> > &matrix) {  
     if (matrix.empty() || matrix[0].empty()) return 0;        
     int M = matrix.size();  
     int N = matrix[0].size();  
     vector<int> height(N + 1, 0); // one more element added  
     int res = 0;  
     for (int i = 0; i < M; ++i) {  
       for (int j = 0; j < N; ++j) {  
         height[j] = (matrix[i][j] == '0') ? 0 : height[j] + 1;          
       }  
       res = max(res, largestRectangleArea(height));  
     }  
     return res;  
   }  
     
   // a little different from 'Largest Rectangle in Histogram'  
   // final 0 is already provided beforehand  
   int largestRectangleArea(const vector<int> &height) {  
     stack<int> stk;  
     int res = 0, i = 0, N = height.size();  
     while (i < N) {  
       if (stk.empty() || height[stk.top()] <= height[i])  
         stk.push(i++);  
       else {  
         int index = stk.top(); stk.pop(); // stack update  
         int width = stk.empty() ? i : i - stk.top() - 1; // stk.top must be descending order  
         res = max(res, width * height[index]);  
       }  
     }  
     return res;  
   }  
 };  

Simplify Path

来源：Leetcode

原帖：http://oj.leetcode.com/problems/simplify-path/

题目：
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
Solution: Add an additional '/' at the end of 'path' for simply detecting the end.
/./ not change the path.

代码：

 class Solution {  
 public:  
   //使用栈来记录字符串结果，当遇到/../时，弹出栈  
   //如果用一个栈来一次存储各级路径的directory名字，然后重组，会简便一些，这也是文件路径简化类题目的常用思路。  
   //为了末尾可以顺序遍历栈重组path，我们不用传统的stack lib，而用vector来实现栈，这样可以方便顺序遍历。  
   string simplifyPath(string path) {  
     string result;  
     path.append("/");  
     vector<string> paths;  
     size_t pos = path.find_first_of("/");  
     size_t last = 0;  
     while (pos != string::npos) {  
       string substr = path.substr(last, pos - last);  
       if (substr == "..") {  
         if (!paths.empty()) {  
           paths.pop_back();  
         }  
       } else if (!substr.empty() && substr != ".") {  
         paths.push_back(substr);  
       }  
       last = pos + 1;  
       pos = path.find_first_of("/", last); // "last" position  
     }  
     if (paths.empty()) return "/";  
     for (auto s : paths) {  
       result += "/" + s;  
     }  
     return result;  
   }  
 };  
   
 class Solution {  
 public:  
   string simplifyPath(string path) {  
     vector<string> dirs;  
     path += '/';  
     string cur;  
     for (auto c : path) {  
       if (c != '/') {  
         cur += c;    
       } else {  
         if (cur == "..") {  
           if (!dirs.empty()) {  
             dirs.pop_back();  
           }  
         } else if(cur != "." && !cur.empty()){// cur != ""很重要.  
           dirs.push_back(cur);  
         }  
         cur.clear();  
       }  
     }  
     if (dirs.empty()) return "/";  
     string res;  
     for (auto dir : dirs) {  
       res += "/" + dir;  
     }  
     return res;  
   }  
 };  

Valid Parentheses

来源：Leetcode

原帖：http://oj.leetcode.com/problems/valid-parentheses/

题目：
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

代码：

 class Solution {  
 public:  
   bool isValid(string s) {  
     stack<char> stk;  
     for (int i = 0; i < s.size(); ++i) {  
       if (s[i] == '(' || s[i] == '[' || s[i] == '{') {  
         stk.push(s[i]);  
       } else {  
         if (stk.empty() || abs(stk.top() - s[i]) > 2) { // match text?   
           return false;  
         }  
         stk.pop();  
       }  
     }    
     return stk.empty();  
   }  
 };  

150 Evaluate Reverse Polish Notation

来源：Leetcode

原帖：https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

题目：
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
(http://en.wikipedia.org/wiki/Reverse_Polish_notation)
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

代码：

 class Solution {  
 public:  
   int evalRPN(vector<string> &tokens) {  
     stack<int> s;  
     for (int i = 0; i < tokens.size(); ++i) {  
       if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {  
         s.push(stoi(tokens[i])); // string to int          
       } else {  
         int op2 = s.top();s.pop();  
         int op1 = s.top();s.pop();  
         int result = 0;          
         if (tokens[i] == "+") {  
           result = op1 + op2;            
         } else if (tokens[i] == "-") {  
           result = op1 - op2;            
         } else if (tokens[i] == "*") {  
           result = op1 * op2;            
         } else if (tokens[i] == "/") {  
           result = op1 / op2;            
         }  
         s.push(result);  
       }  
     }  
     return s.top();  
   }  
 };  

Binary Tree Preorder Traversal

来源：Leetcode

原帖：http://oj.leetcode.com/problems/binary-tree-preorder-traversal/

题目：
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
    1
     \
      2
     /
    3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

Solution: 1. Recursive solution.      Time: O(n), Space: O(n).
           2. Iterative way (stack).   Time: O(n), Space: O(n).
           3. 更简单的使用 http://answer.ninechapter.com/solutions/binary-tree-preorder-traversal/
           4. Threaded tree (Morris).  Time: O(n), Space: O(1). // 面试应该不会用到
           http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

代码：

 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
   
 class Solution {  
 public:    
   vector<int> preorderTraversal(TreeNode *root) {  
     vector<int> res;  
     preorderTraversalHelper(root, res);  
     return res;  
   }  
   
   void preorderTraversalHelper(TreeNode *node, vector<int> &res) {  
     if (!node) return;  
     res.push_back(node->val);  
     preorderTraversalHelper(node->left, res);  
     preorderTraversalHelper(node->right, res);  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: iterative + stack  
   vector<int> preorderTraversal(TreeNode *root) {  
     vector<int> res;  
     stack<TreeNode*> stk; // stack  
     TreeNode *cur = root; // cur pointer  
     while (cur || !stk.empty()) {  
       if (cur) {  
         res.push_back(cur->val);  
         stk.push(cur);  
         cur = cur->left;  
       } else if (!stk.empty()) {  
         cur = stk.top()->right;  
         stk.pop();  
       }  
     }  
     return res;  
   }  
 };  
     
 class Solution {  
 public:   
   //Version 3: 更简单的递归做法  
   vector<int> preorderTraversal(TreeNode *root) {  
     vector<int> path;  
     stack<TreeNode*> s;  
     s.push(root);  
     while (!s.empty()) {  
       root = s.top();  
       s.pop();  
       if (root == NULL) {  
         continue;  
       } else {  
         path.push_back(root->val);  
         s.push(root->right);  
         s.push(root->left);  
       }  
     }  
     return path;  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 4: Morris (Thread) tree  
   vector<int> preorderTraversal(TreeNode *root) {  
     vector<int> res;  
     TreeNode *cur = root;  
     while (cur) {  
       if (cur->left) {  
         TreeNode *prev = cur->left;  
         while (prev->right && prev->right != cur) { // find predecessor   
           prev = prev->right;  
         }  
             
         if (prev->right == cur) { // 2.b  
           cur = cur->right;  
           prev->right = NULL;  
         } else { // prev->right = NULL 2.a  
           res.push_back(cur->val); // only difference with inorder traversal  
           prev->right = cur;  
           cur = cur->left;  
         }  
       } else { // 1.  
         res.push_back(cur->val);  
         cur = cur->right;  
       }  
     }  
     return res;  
   }  
 };  

Maximum Rectangle in Histogram

来源：Twitter Phone Interview，Leetcode

原帖：https://leetcode.com/problems/largest-rectangle-in-histogram/

题目：
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

思路：
Twitter first round phone interview。使用stack保存栈内递增序列，原数组需要加入一个最小值-1，保持栈内元素能够完全清空。

代码：

 class Solution {  
 public:  
     //stack keeps increasing/decreasing order numbers.   
     //for example: 2 1 8 9 4 5 3   
     //寻找i左侧比A[i]大的第一个数  
     int largestRectangleArea(vector<int> &height) {  
         if (height.empty()) return 0;  
         stack<int> s;  
         height.push_back(-1); //辅助空间，帮助把栈内所有元素pop  
         int maxRect = 0;  
         int i = 0, size = height.size();  
         while (i < size) {  
             if (s.empty() || height[s.top()] <= height[i]) { // left search  
                 s.push(i++);  
             } else { // right search  
                 int h = height[s.top()]; s.pop(); // stk.top()保存可以作为矩形顶点的最大高度, then s.pop()  
                 int w = s.empty() ? i : i - s.top() - 1; // s.top() is left boundary; i is right boundary  
                 maxRect = max(maxRect, w * h);  
             }  
         }  
         return maxRect;  
     }  
 };