网站建设属于广告费么,网站的设计思想,线下推广渠道和方式,手机网站与普通网站的区别1793. 好子数组的最大分数
给你一个整数数组nums#xff08;下标从0开始#xff09;和一个整数k。
一个子数组(i, j)的 分数 定义为min(nums[i], nums[i1], ..., nums[j]) * (j - i 1)。一个 好 子数组的两个端点下标需要满足i k j。
请你返回 好 子数组的最大…1793. 好子数组的最大分数
给你一个整数数组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 。 题目分析
单调栈
解题思路
维持一个单调递减栈用于存储数组元素的下标遍历数组 nums对于每个元素 nums[i]执行以下步骤 如果栈不为空且当前元素 nums[i] 小于栈顶元素对应的值 nums[stack.peek()]说明栈顶元素无法成为好子数组的右端点了。此时需要将栈顶元素出栈并计算以栈顶元素为右端点的最大可能分数。分数计算公式为nums[stack.pop()] * (i - stack.peek() - 1)将当前元素下标 i 入栈 遍历完成后清空栈此时右端点为nums.length - 1 单调栈详解及相关 Leetcode 题解见 Leetcode 单调栈详解 class Solution {public int maximumScore(int[] nums, int k) {int ans 0;// 单调递减栈StackInteger stack new Stack();for (int i 0; i nums.length; i) {while (!stack.isEmpty() nums[stack.peek()] nums[i]) {int h nums[stack.pop()];int left stack.isEmpty() ? 0 : stack.peek() 1;int right i - 1;int w right - left 1;if (left k k right) {ans Math.max(ans, w * h);}}stack.push(i);}while (!stack.isEmpty()) {int h nums[stack.pop()];int right nums.length - 1;int left stack.isEmpty() ? 0 : stack.peek() 1;int w right - left 1;if (left k k right) {ans Math.max(ans, w * h);}}return ans;}
}
双指针
解题思路以下标为k的元素作为中心向两边扩展每次扩展一个单位。取左右边界的较大者作为下一个要扩展的区域。
[left, right] 表示下标 left 到 right 的区域为已经扩展过的区间curValue (right - left 1) * min 表示包含 k 在内且区间长度为 (right - left 1) 的最大值 双指针顾名思义就是同时使用两个指针在序列、链表结构上指向的是位置在树、图结构中指向的是节点通过或同向移动或相向移动来维护、统计信息 class Solution {public int maximumScore(int[] nums, int k) {int n nums.length;int ans nums[k];int min nums[k];int left k;int right k;while (left 0 || right 1 n) {if (right 1 n || (left 0 nums[left - 1] nums[right 1])) {left--;min Math.min(min, nums[left]);} else {right;min Math.min(min, nums[right]);}ans Math.max(ans, (right - left 1) * min);}return ans;}
}
