直方图最大矩形覆盖（单调栈stack）

链接LintCode 炼码 - ChatGPT更高效的学习体验题解这是一个单调递增栈弹出的元素保证从当前位置向后扫能构成矩形九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧保持单调递增栈顶元素弹出的时候可以计算以栈顶元素为宽的最大矩形弹出的时候可以知道左右两边比自己小的位置在哪里这样就可以构造出以当前位置为height的最大矩形class Solution { public: /** * param heights: A list of integer * return: The area of largest rectangle in the histogram */ int largestRectangleArea(vectorint heights) { // write your code here if (heights.size() 0) { return 0; } std::stackint sta; int result 0; for (int i 0; i heights.size(); i) { int cur_height i heights.size() ? -1 : heights[i]; while (!sta.empty() cur_height heights[sta.top()]) { int top sta.top(); sta.pop(); int h heights[top]; int w sta.empty() ? i : i - sta.top() - 1; result max(result, h * w); } sta.push(i); } return result; } };