84. 柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?source=vscode

 

建议这两个一起服用

https://www.cnblogs.com/WTSRUVF/p/19045624

https://www.cnblogs.com/WTSRUVF/p/19006576

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

解析：

单调栈的意义：

1. 顺序保持：单调栈能保持元素的相对顺序，适用于需要保留顺序关系的问题。
2. 快速访问：通过单调性质，能够快速访问需要的比当前元素大或小的元素（比如左右两边第一个比自己大或者小的元素）。

回到这个题，首先对每个元素，都以自己为基准看最长左右两边能扩展到哪里，其实就是求左右两边第一个比自己小的元素位置

那就保持递增栈，入栈后，前一个元素就是左边第一个比自己小的，被出栈时，入栈的元素就是右边第一个比自己小的

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;heights.push_back(-1);int n = heights.size();st.push(0);int max_area = -1;for (int i = 1; i < n; i++) {while(!st.empty() && heights[st.top()] >= heights[i]) {int j = st.top();st.pop();int left = -1;if (!st.empty()) left = st.top();max_area = max(max_area, (i - left - 1) * heights[j]);}st.push(i);}return max_area;}
};