网站建设公司被网监大队检查,seo流量工具,劳务公司怎么注册需要什么要求,花卉网站建设策划书84.柱状图中最大的矩形
84. 柱状图中最大的矩形 - 力扣#xff08;LeetCode#xff09; 思路
本题是要找每个柱子左右两边第一个小于该柱子的柱子#xff0c;所以从栈头#xff08;元素从栈头弹出#xff09;到栈底的顺序是从大到小的顺序。例#xff1a; 三种情况LeetCode 思路
本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序是从大到小的顺序。例 三种情况
情况一当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况情况二当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况情况三当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
class Solution {
public:int largestRectangleArea(vectorint heights) {int result 0;stackint st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈从下标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(); // 这个可以加可以不加效果一样思路不同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;}
};双指针解法
class Solution {
public:int largestRectangleArea(vectorint heights) {vectorint minLeftIndex(heights.size());vectorint minRightIndex(heights.size());int size heights.size();// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] -1; // 注意这里初始化防止下面while死循环for (int i 1; i size; i) {int t i - 1;// 这里不是用if而是不断向左寻找的过程while (t 0 heights[t] heights[i]) t minLeftIndex[t];minLeftIndex[i] t;}// 记录每个柱子 右边第一个小于该柱子的下标minRightIndex[size - 1] size; // 注意这里初始化防止下面while死循环for (int i size - 2; i 0; i--) {int t i 1;// 这里不是用if而是不断向右寻找的过程while (t size heights[t] heights[i]) t minRightIndex[t];minRightIndex[i] t;}// 求和int result 0;for (int i 0; i size; i) {int sum heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result max(sum, result);}return result;}
};
笔记参考代码随想录
