上海网站建设公司推荐,google谷歌搜索引擎入口,如何制作app图标,网站建设服务商城文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;1793. 好子数组的最大分数
相关题目#xff1a;
[单调栈] lc84. 柱状图中最大的矩形、aw131. 直方图中最大的矩形(单调栈算法对比模板题)
2. 题目解析
一道需要转换思维的题目#xff0c;需要将其转换为1793. 好子数组的最大分数
相关题目
[单调栈] lc84. 柱状图中最大的矩形、aw131. 直方图中最大的矩形(单调栈算法对比模板题)
2. 题目解析
一道需要转换思维的题目需要将其转换为柱状图中的最大矩形的题目 可以看看图形和这个题目的描述即可。
转换之后就是一道标准的单调栈应用的题目了。需要找到两侧第一个小于该位置的下标即可记为 l, r。那么矩形的高度记为当前位置的高度宽度即为 r-l-1。因为这里是严格小于的高度矩形边界不为 l, r所以需要 -1。单调栈在编写的时候需要注意 l, r 数组的边界情况当栈中无元素时记得向 l, r 中添加边界值。
这里也是额外多了一个限制要求下标 k 要在矩形中注意边界判断的时候不能取 号。
题目中还提到了双指针的优雅做法。但是思路比较精妙不容易想出不容易借鉴感兴趣去参考题解区吧。 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) class Solution {
public:int maximumScore(vectorint nums, int k) {int n nums.size();vectorint l(n), r(n);stackint s;for (int i 0; i n; i ) {while (s.size() nums[s.top()] nums[i]) s.pop();if (s.size()) l[i] s.top();else l[i] -1;s.push(i);}s stackint();for (int i n - 1; ~i; i -- ) {while (s.size() nums[s.top()] nums[i]) s.pop();if (s.size()) r[i] s.top();else r[i] n;s.push(i);}int res 0;for (int i 0; i n; i ) {int il l[i], ir r[i];if (il k k ir) res max(res, (ir - il - 1) * nums[i]);}return res;}
};
