84 柱狀圖中最大的矩形

題目鏈接：84. 柱狀圖中最大的矩形 - 力扣（LeetCode）

給定?n?個非負(fù)整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區(qū)域，面積為 10

思路：使用left、right分別記錄每個元素左邊比它小和右邊比它小的位置。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> left(heights.size(), -1);vector<int> right(heights.size(), heights.size());stack<int> s;int result = 0;//rightfor(int i = 0; i < heights.size(); i++){while(!s.empty() && heights[i] < heights[s.top()]){right[s.top()] = i;s.pop();}s.push(i);}while(!s.empty()) { s.pop();}//leftfor(int i = heights.size() - 1; i >= 0; i--){while(!s.empty() && heights[i] < heights[s.top()]){left[s.top()] = i;s.pop();}s.push(i);}for(int i = 0; i < heights.size(); i++){result = max(result, (right[i] - left[i] - 1) * heights[i]);}return result;}
};