本文主要是介绍[M单调栈] lc1793. 好子数组的最大分数(单调栈+双指针+思维转换),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接: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(vector<int>& nums, int k) {int n = nums.size();vector<int> l(n), r(n);stack<int> 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 = stack<int>();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;}
};
这篇关于[M单调栈] lc1793. 好子数组的最大分数(单调栈+双指针+思维转换)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!