2024.3.19力扣每日一题——好子数组的最大分数

本文主要是介绍2024.3.19力扣每日一题——好子数组的最大分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

力扣每日一题；题序：1793

我的题解

方法一 双指针

左右指针初始指向k-1,k+1，表示左右边界。参考官方题解
好子数组必须要包含 nums[k]，那么我们可以使用两个指针 left 和 right 表示选择的子数组为 (left,right)（左开右开），且 left 和 right的初始值为 k−1 和 k+1。
随后可以枚举子数组分数定义中 min⁡{⋯ } 部分的值。它的最大值为 nums[k]，最小值为数组 nums中的最小值。随后更新i为左右边界的最大值，可以不断向左移动 left，或者向右移动 right，直到：

• 指针超出数组的边界，或者
• 指针指向的元素小于 iii，分数定义中的 min⁡{⋯ } 的值发生了变化。

当移动完成后，(left,right) 就是最小值大于等于 i 的一个子数组，它的分数至少为：(right−left−1)×i
当 i恰好是 (left,right) 的最小值时，上式就是它对应的分数。当 i 继续减少但指针没有移动时，上式计算出的分数会比正确的分数要低，但一定不会更高。因此，只要在枚举的过程中维护上式的最大值，就可以得到正确的答案。
当两个指针都超出数组的边界时，就可以结束枚举并返回答案。

时间复杂度：O(n)
空间复杂度：O(1)

    public int maximumScore(int[] nums, int k) {int n = nums.length;int left = k - 1, right = k + 1;int ans = 0;for (int i = nums[k];; ) {while (left >= 0 && nums[left] >= i) {--left;}while (right < n && nums[right] >= i) {++right;}ans = Math.max(ans, (right - left - 1) * i);if (left == -1 && right == n) {break;}//更新i为左右边界的最大值i=Math.max((left==-1?-1:nums[left]),(right==n?-1:nums[right]));if(i==-1)break;}return ans;}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

这篇关于2024.3.19力扣每日一题——好子数组的最大分数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---