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

  |  

摘要: 一个单调栈的难题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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