单调栈

给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。
简单的例子：input: 5,3,1,2,4return: -1 3 1 1 -1

code

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;
}

T2

int largestRectangleArea(vector<int> &height) {
            int ret = 0;
            height.push_back(0);
            vector<int> index;
            for(int i = 0; i < height.size(); i++) {
                while(index.size() > 0 && height[index.back()] >= height[i]) {
                    int h = height[index.back()];
                    index.pop_back();
                    int sidx = index.size() > 0 ? index.back() : -1;
                    ret = max(ret, h * (i-sidx-1));
                }
                index.push_back(i);
            }
            return ret;
        }

T3

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
return 6

int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty())  return 0;
        vector<int> height(matrix[0].size(), 0);
        int maxRect= 0;
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < height.size(); ++j) {
                if(matrix[i][j] == '0')    height[j] = 0;
                else    ++height[j];
            }
            maxRect = max(maxRect, largestRectangleArea(height));
            height.pop_back();
        }
        return maxRect;
    }
    int largestRectangleArea(vector<int> &height) {
            int ret = 0;
            height.push_back(0);
            vector<int> index;
            for(int i = 0; i < height.size(); i++) {
                while(index.size() > 0 && height[index.back()] >= height[i]) {
                    int h = height[index.back()];
                    index.pop_back();
                    int sidx = index.size() > 0 ? index.back() : -1;
                    ret = max(ret, h * (i-sidx-1));
                }
                index.push_back(i);
            }
            return ret;
    }