84.柱状图中最大的矩形
要求：
有多个矩形，要求返回可能勾勒出的最大矩形思路：
寻找右边第一个小于当前节点的index 寻找左边第一个小于当前节点的index 右边：累加的方式，如果当前节点小于，那么判读后放进去 左边，放进去了之后，当前节点后一个，就是左边最小的代码：
1 // 要求：和相邻节点比对，找出最大的面积
2 //
3 // 难点：大于等于当前节点连续的柱子长度
4 // 思路：左边第一个小于当前节点的，和右边第一个小于当前节点的
5 //
6 // 高度：当前节点
7 // 长度：左边第一个小于当前节点的 右边第一个小于当前节点
8 //
9 int largestRectangleArea(vector<int>& heights) {
10 if (heights.size() == 1)return heights[0];
11
12 int result = 0;
13 vector<int> right_indexs(heights.size(), heights.size());
14 vector<int> left_indexs(heights.size(), -1);
15 deque<int> st;
16
17 st.push_back(0);
18 for (int i = 1; i < heights.size(); i++)
19 {
20 if (heights[i] < heights[st.back()])
21 {
22 while (!st.empty() && heights[i] < heights[st.back()])
23 {
24 right_indexs[st.back()] = i;
25 st.pop_back();
26 }
27 }
28
29 if (st.empty()) left_indexs[i] = -1;
30 else left_indexs[i] = st.back();
31
32 st.push_back(i);
33 }
34
35
36 for (int i = 0; i < heights.size(); i++)
37 {
38 cout << left_indexs[i] << " " << right_indexs[i] << endl;
39 int cur = heights[i] * (right_indexs[i] - left_indexs[i] -1);
40
41 result = result > cur ? result : cur;
42 }
43
44 return result;
45 }
标签：第四十六,随想录,back,st,柱状图,indexs,heights,节点,size From： https://www.cnblogs.com/smartisn/p/17607583.html