柱状图中最大的矩形 - 困难
*************
c++
topic: 84. 柱状图中最大的矩形 - 力扣（LeetCode）
*************
chenck the topic first:
 |
Think about the topics I have done before. the rains project comes:盛最多水的容器 - 中等难度-CSDN博客
https://blog.csdn.net/ElseWhereR/article/details/144420793?spm=1001.2014.3001.5501
Double pointer was used. Here in this project double can be used to.
The most important is to caculate the area. So named variable area is area. Initialize the area 0.
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int area = 0;
// do something here
}
};area = length × heigth;
height is eazy to be seen which is min(heights[i], height[j]);
length is easy too which is j - i + 1;
next step is how to loop?
refer to the rains problem:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
int max_area = 0;
for (int i = 0; i < n; i++) {
int minHeight = heights[i]; // 初始化最小高度为当前柱子的高度
for (int j = i; j >= 0; j--) { // 内层循环应从i向左遍历
if (heights[j] < minHeight) {
minHeight = heights[j];
}
int width = i - j + 1;
int area = minHeight * width;
if (area > max_area) {
max_area = area;
}
}
}
return max_area;
}
};and overtime comes like old friend:
aesthetics of violence always works.
Change the way to reduce the loop times.
Introduce Mr. Stack:
not that stack, but this stack:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h = (i < n) ? heights[i] : 0;
while (!s.empty() && h < heights[s.top()]) {
int top = s.top();
s.pop();
int left = s.empty() ? -1 : s.top();
int width = i - left - 1;
int area = heights[top] * width;
max_area = max(max_area, area);
}
s.push(i);
}
return max_area;
}
};In c++, stack means one type of data structure. The stack structure is used to 存储函数调用时的参数、局部变量和返回地址。每当一个函数被调用时，相关的信息被压入栈中；当函数执行完毕后，这些信息被弹出栈，以便返回到调用函数。
Stack kickss pointer j out.
- The important thing is making a stack, the stack is progressive increase.
- When a height smaller than the top of the stack is encountered, the top of the stack is popped and the area of the rectangle with that height as the lowest is calculated.
- refresh the max_area.
For example:
heights = [2, 1, 5, 6, 2, 3]
| i | 0 | 1 | 2 | 3 | 4 | 5 |
| h | 2 | 1 | 5 | 6 | 2 | 3 |
-
-
i = 0:
-
h = heights[0] = 2。 -
栈为空，直接压入0，栈 = [0]。
-
-
i = 1:
-
h = heights[1] = 1。 -
1 < heights[0] = 2，弹出0，计算面积：
-
left = -1，width = 1 - (-1) - 1 = 1，area = 2 * 1 = 2。
-
-
压入1，栈 = [1]。
-
-
i = 2:
-
h = heights[2] = 5。 -
5 >= heights[1] = 1，直接压入2，栈 = [1, 2]。
-
-
i = 3:
-
h = heights[3] = 6。 -
6 >= heights[2] = 5，直接压入3，栈 = [1, 2, 3]。
-
-
i = 4:
-
h = heights[4] = 2。 -
2 < heights[3] = 6，弹出3，计算面积：
-
left = 2，width = 4 - 2 - 1 = 1，area = 6 * 1 = 6，max_area = 6。
-
-
2 < heights[2] = 5，弹出2，计算面积：
-
left = 1，width = 4 - 1 - 1 = 2，area = 5 * 2 = 10，max_area = 10。
-
-
压入4，栈 = [1, 4]。
-
-
i = 5:
-
h = heights[5] = 3。 -
3 >= heights[4] = 2，直接压入5，栈 = [1, 4, 5]。
-
-
i = 6:
-
h = 0。 -
0 < heights[5] = 3，弹出5，计算面积：
-
left = 4，width = 6 - 4 - 1 = 1，area = 3 * 1 = 3，max_area = 10。
-
-
0 < heights[4] = 2，弹出4，计算面积：
-
left = 1，width = 6 - 1 - 1 = 4，area = 2 * 4 = 8，max_area = 10。
-
-
0 < heights[1] = 1，弹出1，计算面积：
-
left = -1，width = 6 - (-1) - 1 = 6，area = 1 * 6 = 6，max_area = 10。
-
-
压入6，栈 = [6]。
-
-
-
返回最大面积：
-
max_area = 10。
-
It works. And the next step is to write the code:
the first is to innitialize some variable
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
// do something here
}
};and caculate the area :
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
// do something here
int area = heights[top] * width; // caculate the area
max_area = max(max_area, area); // fresh the max area
}
};how to find the width?
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
// do something here
int width = i - left - 1; // find the width
int area = heights[top] * width; // caculate the area
max_area = max(max_area, area); // fresh the max area
}
};and what is left?
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
// do something here
int left;
if (s.empty()) {
left = -1;
} else {
left = s.top();
}
int width = i - left - 1; // find the width
int area = heights[top] * width; // caculate the area
max_area = max(max_area, area); // fresh the max area
}
};make the loop
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h;
if (i < n) {
h = heights[i];
} else {
h = 0;
}
int left;
if (s.empty()) {
left = -1;
} else {
left = s.top();
}
int width = i - left - 1; // find the width
int area = heights[top] * width; // calculate the area
max_area = max(max_area, area); // refresh the max area
} else {
break; // 如果h不小于栈顶元素的高度，退出循环
}
}
return max_area;
}
};int h
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s; // 存储柱子的下标
int max_area = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h;
if (i < n) {
h = heights[i];
} else {
h = 0;
}
while (true) {
if (!s.empty()) {
if (h < heights[s.top()]) {
int top = s.top();
s.pop(); // kick your ass
int left;
if (s.empty()) {
left = -1;
} else {
left = s.top();
}
int width = i - left - 1; // find the width
int area = heights[top] * width; // calculate the area
max_area = max(max_area, area); // refresh the max area
} else {
break; // 如果h不小于栈顶元素的高度，退出循环
}
} else {
break; // 如果栈为空，退出循环
}
}
s.push(i); // add it
}
return max_area;
}
};done