单调栈为什么要用栈来存储之前遍历过的元素而不用普通数组
时间: 2023-10-26 11:04:44 浏览: 49
单调栈中使用栈来存储之前遍历过的元素,是因为单调栈需要满足栈内元素的单调性,即栈内元素保持单调递增或单调递减的性质。如果使用普通数组来存储之前遍历过的元素,那么每次要维护栈内元素的单调性时,需要进行大量的元素移动,效率较低。
而使用栈来存储元素,则可以快速地进行栈内元素的插入和删除,使得栈内元素始终保持单调性。同时,栈具有后进先出的特点,可以方便地回溯之前遍历过的元素,满足单调栈的操作需求。
因此,单调栈中使用栈来存储之前遍历过的元素,可以提高算法的效率,并且更加方便地满足单调栈的操作需求。
相关问题
C++单调栈输入一个由0和1组成的数组,计算全为1的最大矩形的面积
可以使用单调栈来解决这个问题。
具体来说,我们可以维护一个单调递增栈,其中存储的是数组中元素的下标。遍历数组中的每个元素,如果当前元素小于或等于栈顶元素对应的元素,则将栈顶元素弹出,并且计算以该元素为右边界、以弹出的元素为左边界的最大矩形面积。计算完之后,将当前元素入栈。如果当前元素大于栈顶元素对应的元素,则将当前元素入栈。
在遍历完整个数组之后,栈中剩余的元素对应的矩形面积也可以进行计算。
以下是C++代码实现:
```C++
#include <iostream>
#include <stack>
using namespace std;
int getMaxArea(int hist[], int n) {
stack<int> s;
int max_area = 0;
int tp;
int area_with_top;
int i = 0;
while (i < n) {
if (s.empty() || hist[s.top()] <= hist[i]) {
s.push(i++);
} else {
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top) {
max_area = area_with_top;
}
}
}
while (!s.empty()) {
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top) {
max_area = area_with_top;
}
}
return max_area;
}
int main() {
int hist[] = { 0, 1, 1, 0, 1, 1, 1, 0 };
int n = sizeof(hist) / sizeof(hist[0]);
cout << "Maximum area is " << getMaxArea(hist, n);
return 0;
}
```
输出结果为:
```
Maximum area is 6
```
因此,全为1的最大矩形的面积为6。
C++单调栈手动输入一个由0和1组成的数组,计算全为1的最大矩形的面积
以下是C++代码实现:
```c++
#include <iostream>
#include <stack>
using namespace std;
int getMaxArea(int hist[], int n) {
stack<int> s;
int max_area = 0;
int tp;
int area_with_top;
int i = 0;
while (i < n) {
if (s.empty() || hist[s.top()] <= hist[i]) {
s.push(i++);
}
else {
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
}
while (s.empty() == false) {
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
int main() {
int n;
cout << "请输入数组大小:";
cin >> n;
int hist[n];
cout << "请输入数组元素(0/1):" << endl;
for (int i = 0; i < n; i++) {
cin >> hist[i];
}
cout << "全为1的最大矩形面积为:" << getMaxArea(hist, n) << endl;
return 0;
}
```
代码思路:
1. 使用单调栈存储数组元素的下标,遍历整个数组。
2. 如果栈为空或当前元素大于等于栈顶元素,则将当前元素下标入栈。
3. 如果当前元素小于栈顶元素,则弹出栈顶元素,并计算以该元素高度为高的最大面积。面积的计算方法为:弹出元素的高度 * (右边第一个小于该元素的元素下标 - 左边第一个小于该元素的元素下标 - 1)。
4. 如果当前计算出的面积大于之前的最大面积,则更新最大面积。
5. 遍历完数组后,如果栈中还有元素,则按照步骤3计算面积并更新最大面积。
6. 返回最大面积。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)