算法leetcode

力扣1793-好子数组的最大分数

字数统计: 814字   |   阅读时长: 3分
,

摘要: 一个单调栈的难题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文回顾一个此前解决过的一个单调栈的难题。这是 232 场周赛的 D 题。在周赛的 D 题中以单调栈为核心考点还是比较少见的，让我们看看这道题难在哪。

关于单调栈的基础知识，可以参考文章 单调栈, 在文章 单调栈题目汇总 中我们也总结了单调栈的常见题目，可以参考。

$1 题目

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

提示：

1
2
3
1 <= nums.length <= 105
1 <= nums[i] <= 2 * 104
0 <= k < nums.length

示例 1：
输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) (5-1+1) = 3 5 = 15 。

示例 2：
输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) (4-0+1) = 4 5 = 20 。

$2 题解

算法: 单调栈

要最大化的是区间 [i, j] 上的最小值乘以区间长度。

答案一定是某个最小值乘以某个覆盖了该最小值区间长度的乘积。

对每个数 nums[i]，我们想如果这个数 nums[i] 是某个区间的最小值，那么这个区间可以往两边扩展多远，假设可以扩展到 [j1, j2]，那么 nums[i] * (j2 - j1 + 1) 就是一个可能的答案。

每个数 nums[i] 对应的 nums[i] * (j2 - j1 + 1) 都求完之后，就可以知道最终答案。

对 nums[i]，如果知道其左侧第一个小于 nums[i] 的位置 s1，和右侧第一个小于 nums[i] 的位置 s2，那么 [s1 + 1, j1 - 1] 就是 [j1, j2]，

而给定 i 后【其左侧第一个小于 nums[i] 的位置 s1，和右侧第一个小于 nums[i] 的位置 s2】这步查询可以用单调栈完成，具体可以参考 单调栈。

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        if(nums.empty()) return 0;
        int n = nums.size();
        stack<int> st({-1});
        int result = nums[k];
        for(int i = 0; i < n; ++i)
        {
            if(st.top() == -1 || nums[st.top()] <= nums[i])
                st.push(i);
            else
            {
                while(st.top() != -1 && nums[st.top()] > nums[i])
                {
                    int index = st.top();
                    st.pop();
                    if((i - 1) >= k && (st.top() + 1) <= k)
                    {
                        int w = i - st.top() - 1;
                        int area = w * nums[index];
                        result = max(result, area);
                    }
                }
                st.push(i);
            }
        }
        while(st.top() != -1)
        {
            int index = st.top();
            st.pop();
            if((st.top() + 1) <= k)
            {
                int w = n - st.top() - 1;
                int area = w * nums[index];
                result = max(result, area);
            }
        }
        return result;
    }
};
Share