单调栈

单调栈理解起来很容易，但是实际运用却没那么简单。一句话解释单调栈，就是一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性。

下面结合题目，在实战中学会使用单调栈解决问题。

Google面试题

(google面试)题目: 给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。

简单的例子：

input: 5,3,1,2,4

return: -1 3 1 1 -1

解决方案：递减栈

implementation:

vector<int> nextExceed(vector<int> &input) {
	vector<int> result (input.size(), -1);
	stack<int> monoStack;
	for(int i = 0; i < input.size(); ++i) {	
		while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
			result[monoStack.top()] = i - monoStack.top();
			monoStack.pop();
		}
		monoStack.push(i);
	}
	return result;
}

LeetCode-42

题目: LeetCode-42. Trapping Rain Water

解决方案：递减栈

implementation:

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> st(height.size());
        int head = -1;
        int res = 0;
        for (int i = 0; i < height.size(); i++) {
            while (head >= 0 && height[st[head]] <= height[i]) {
                if (st[head] + 1 != i) {
                    res += (height[st[head]] - height[st[head + 1]]) * (i - st[head] - 1);
                }    
                head--;
            }
            if (head >= 0) res += (height[i] - height[st[head + 1]]) * (i - st[head] - 1);
            st[++head] = i;
        }
        return res;
    }
};

LeetCode-84

题目：LeetCode-84. 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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

解决方案：递增栈

implementation:

int largestRectangleArea(vector<int> &height) {
    int ret = 0;
    height.push_back(0);
    stack<int> index;
    for(int i = 0; i < height.size(); i++) {
        while(index.size() > 0 && height[index.top()] > height[i]) {
            // 计算以index.top()为轴的矩形大小,左右两边是已从栈中弹出的比index.top()高的小矩形
            int h = height[index.top()];
            index.pop();
            int idx = index.empty() ? -1 : index.top();
            ret = max(ret, (i - idx - 1) * h);
        }
        index.push(i);
    }
    return ret;
}

LeetCode-85

题目: LeetCode-85. Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

implementation:

方法一: 单调递增栈(20ms)
实质上与LeetCode-84求最大矩形面积等价,通过迭代行来更新高度数组

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> height(n, 0);
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') height[j] = 0;
                else height[j]++;
            }
            ret = max(ret, largestRectangleArea(height));
        }
        return ret;
    }
private:
    int largestRectangleArea(vector<int> &height) {
        int ret = 0;
        height.push_back(0);
        stack<int> index;
        for(int i = 0; i < height.size(); i++) {
            while(index.size() > 0 && height[index.top()] > height[i]) {
                int h = height[index.top()];
                index.pop();
                int idx = index.empty() ? -1 : index.top();
                ret = max(ret, (i - idx - 1) * h);
            }
            index.push(i);
        }
        height.pop_back();
        return ret;
    }
};

方法二：动态规划dp(16ms)
lefts[j]和rights[j]分别存储以height[j]为高度的矩阵的左边界和右边界

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n, 0), lefts(n, 0), rights(n, n);
        int ret = 0;
        for (int i = 0; i < m; i++) {
            int cur_left = 0, cur_right = n;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') heights[j] = 0;
                else heights[j]++;
                if (heights[j] > 0) {
                    lefts[j] = max(cur_left, lefts[j]);
                } else {
                    lefts[j] = 0;
                    cur_left = j + 1;
                }
            }
            for (int j = n - 1; j >= 0; j--) {
                if (heights[j] > 0) {
                    rights[j] = min(cur_right, rights[j]);
                } else {
                    rights[j] = n;
                    cur_right = j;
                }
            }
            for (int j = 0; j < n; j++) {
                ret = max(ret, (rights[j] - lefts[j]) * heights[j]);
            }
        }
        return ret;
    }
};

方法三：暴力枚举(60ms)

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n, 0);
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0'){
                    heights[j] = 0;
                    continue;
                } else heights[j]++;
                int min_height = heights[j];
                for (int k = j; k >= 0; k--) {
                    min_height = min(heights[k], min_height);
                    ret = max(ret, (j - k + 1) * min_height);
                }
            } 
        }
        return ret;
    }
};