企业网站优化搜行者seo,阿里ace wordpress,柳州关键词优化网站,检察机关加强网站建设文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums #xff08;下标从 0 开始#xff09;和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], ..., nums[j]) * (j - i 1) 。一个 好 子数组的两个端点下标需要满足 i k j 。
请你返回…
文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums 下标从 0 开始和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], ..., nums[j]) * (j - i 1) 。一个 好 子数组的两个端点下标需要满足 i k j 。
请你返回 好 子数组的最大可能 分数 。
示例 1
输入nums [1,4,3,7,4,5], k 3
输出15
解释最优子数组的左右端点下标是 (1, 5)
分数为 min(4,3,7,4,5) * (5-11) 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-01) 4 * 5 20 。提示
1 nums.length 10^5
1 nums[i] 2 * 10^4
0 k nums.length来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-score-of-a-good-subarray 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
正反两次单调栈获取以每个数字为最小值的区间 左右界限
class Solution {
public:int maximumScore(vectorint nums, int k) {int n nums.size();vectorint right(n,-1), left(n,-1);stackint s;for(int i n-1; i 0; i--){while(!s.empty() nums[s.top()] nums[i])s.pop();//大于等于我的我是最小的啦删除接着往后找if(!s.empty())right[i] s.top()-1;elseright[i] n-1;s.push(i);}while(!s.empty()) s.pop();for(int i 0; i n; i){while(!s.empty() nums[s.top()] nums[i])s.pop();if(!s.empty())left[i] s.top()1;elseleft[i] 0;s.push(i);}int maxScore 0;for(int i 0; i n; i)if(left[i] k k right[i])maxScore max(maxScore, nums[i]*(right[i]-left[i]1));return maxScore;}
};288 ms 98.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
