餐饮品牌设计包括哪些,公司网站 seo,做百度手机网站优化点,live2d wordpress 插件柱状图中最大的矩形
leetcode链接#xff1a;力扣题目链接
视频链接#xff1a;单调栈#xff0c;又一次经典来袭#xff01; LeetCode#xff1a;84.柱状图中最大的矩形
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;… 柱状图中最大的矩形
leetcode链接力扣题目链接
视频链接单调栈又一次经典来袭 LeetCode84.柱状图中最大的矩形
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。求在该柱状图中能够勾勒出来的矩形的最大面积。这是一道hard题首先是暴力解法任意遍历两个数然后求最值
class Solution {
public:int largestRectangleArea(vectorint heights) {int sum 0;for (int i 0; i heights.size(); i) {int left i;int right i;for (; left 0; left--) {if (heights[left] heights[i]) break;}for (; right heights.size(); right) {if (heights[right] heights[i]) break;}int w right - left - 1;int h heights[i];sum max(sum, w * h);}return sum;}
};如上代码并不能通过leetcode超时了因为时间复杂度是O(n^2)。
双指针法
没想出来直接看题解
难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标而不是左边第一个小于该柱子的高度。
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;}
};单调栈解法
那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序应该是从大到小的顺序
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;}
};这是一道hard题再加上本人临近开学事情比较多先搁置了。二刷具体看思路
