[M单调栈] lc1793. 好子数组的最大分数(单调栈+双指针+思维转换)

本文主要是介绍[M单调栈] lc1793. 好子数组的最大分数(单调栈+双指针+思维转换)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目来源

链接：1793. 好子数组的最大分数

相关题目：

• [单调栈] lc84. 柱状图中最大的矩形、aw131. 直方图中最大的矩形(单调栈+算法对比+模板题)

2. 题目解析

一道需要转换思维的题目，需要将其转换为：柱状图中的最大矩形的题目， 可以看看图形和这个题目的描述即可。

转换之后，就是一道标准的单调栈应用的题目了。需要找到两侧第一个小于该位置的下标即可，记为 l, r。那么矩形的高度记为当前位置的高度，宽度即为 r-l-1。因为这里是严格小于的高度，矩形边界不为 l, r，所以需要 -1。单调栈在编写的时候，需要注意 l, r 数组的边界情况，当栈中无元素时，记得向 l, r 中添加边界值。

这里也是额外多了一个限制，要求下标 k 要在矩形中，注意边界判断的时候不能取 == 号。

题目中还提到了双指针的优雅做法。但是思路比较精妙，不容易想出，不容易借鉴，感兴趣去参考题解区吧。

---

• 时间复杂度：$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. 好子数组的最大分数(单调栈+双指针+思维转换)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---