什么網(wǎng)站可以發(fā)布信息百度推廣效果怎么樣
一、84.柱狀圖中最大的矩形
力扣題目鏈接
42接雨水 是找每個(gè)柱子左右兩邊第一個(gè)大于該柱子高度的柱子,而本題是找每個(gè)柱子左右兩邊第一個(gè)小于該柱子的柱子。
本題是要找每個(gè)柱子左右兩邊第一個(gè)小于該柱子的柱子,所以從棧頭(元素從棧頭彈出)到棧底的順序應(yīng)該是從大到小的順序
主要就是分析清楚如下三種情況:
- 情況一:當(dāng)前遍歷的元素heights[i]大于棧頂元素heights[st.top()]的情況
- 情況二:當(dāng)前遍歷的元素heights[i]等于棧頂元素heights[st.top()]的情況
- 情況三:當(dāng)前遍歷的元素heights[i]小于棧頂元素heights[st.top()]的情況
// 版本一
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(), 0); // 數(shù)組頭部加入元素0heights.push_back(0); // 數(shù)組尾部加入元素0st.push(0);// 第一個(gè)元素已經(jīng)入棧,從下標(biāo)1開始for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) { // 情況一st.push(i);} else if (heights[i] == heights[st.top()]) { // 情況二st.pop(); // 這個(gè)可以加,可以不加,效果一樣,思路不同st.push(i);} else { // 情況三while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};