【LeetCode】5704. 好子数组的最大分数

发表于 更新于 分类于 Valine：
本文字数： 60 阅读时长 ≈ 1 分钟

第232场周赛 5704. 好子数组的最大分数

思路

  1. 单调栈

拓展

  1. 131. 直方图中最大的矩形
  2. 84. 柱状图中最大的矩形
  3. 单调栈模板

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> h(n + 2, -1), l(n + 2), r(n + 2), stk(n + 2);
        for (int i = 1; i <= n; i ++ ) h[i] = nums[i - 1];
        int tt = 0;
        stk[0] = 0;
        for (int i = 1; i <= n; i ++ ) {
            while (h[stk[tt]] >= h[i]) tt -- ;
            l[i] = stk[tt];
            stk[ ++ tt] = i;
        }
        tt = 0, stk[0] = n + 1;
        for (int i = n; i; i -- ) {
            while (h[stk[tt]] >= h[i]) tt -- ;
            r[i] = stk[tt];
            stk[ ++ tt] = i;
        }
        k ++ ;
        int res = 0;
        for (int i = 1; i <= n; i ++ )
            if (l[i] < k && r[i] > k)
                res = max(res, (r[i] - l[i] - 1) * h[i]);
        return res;
    }
};