首页 > 其他分享 >【LeetCode 1793 】好子数组的最高分数

【LeetCode 1793 】好子数组的最高分数

时间:2024-03-19 13:22:39浏览次数:22  
标签:好子 nums 1793 indexes int 数组 ans leftIdx LeetCode

题目描述

原题链接:LeetCode.1793 好子数组的最高分数

解题思路

  • 分数由子数组最小值和长度决定, 而且确定了子数组必须包含nums[k]的值;
  • 从k位置分别向左向右找更小值就是每个子数组的最小值, 左右两端边界下标也就确认了子数组长度;
  • 直观朴素的解法是利用单调栈将向左向右分别严格递减的下标保存起来, 利用栈顶下标对应的最小值和长度依次计算分数;
  • 在上述版本进一步优化代码可以直接去除单调栈, 每次先由上一轮左右边界值确定下一个子数组最小值再扩充至最大长度来计算分数。

解题代码

单调栈保存两端所有可能的最小值下标进行求解:

  /**
   * 双指针单调栈解法,类似于接雨水问题
   * 执行用时: 3 ms , 在所有 Java 提交中击败了 68.92% 的用户
   * 内存消耗: 57.47 MB , 在所有 Java 提交中击败了 9.46% 的用户
   */
  public int maximumScore(int[] nums, int k) {
      int n = nums.length, ans = 0;
      int[] indexes = new int[n];
      indexes[k] = k;
      int leftIdx = k, rightIdx = k;
      // [leftIdx...k]范围保存nums数组中[0...k]范围内严格递增的下标
      for (int i = k - 1; i >= 0; i--) {
          if (nums[i] < nums[indexes[leftIdx]]) {
              indexes[--leftIdx] = i;
          }
      }
      // [k...rightIdx]范围保存nums数组中[k...n)范围内严格递减的下标
      for (int i = k + 1; i < n; i++) {
          if (nums[i] < nums[indexes[rightIdx]]) {
              indexes[++rightIdx] = i;
          }
      }
      // 当前最小值对应的子数组最左和最右边界下标
      int leftBound = 0, rightBound = n - 1;
      while (leftIdx <= k && rightIdx >= leftIdx) {
          if (nums[indexes[leftIdx]] < nums[indexes[rightIdx]]) {
              ans = Math.max(ans, nums[indexes[leftIdx]] * (rightBound - leftBound + 1));
              leftBound = indexes[leftIdx++] + 1;
          }
          else {
              ans = Math.max(ans, nums[indexes[rightIdx]] * (rightBound - leftBound + 1));
              rightBound = indexes[rightIdx--] - 1;
          }
      }
      return ans;
  }

直接双指针确定子数组最左最右边界求解:

  /**
   * 双指针求解
   * 执行用时: 2 ms , 在所有 Java 提交中击败了 100.00% 的用户
   * 内存消耗: 56.03 MB , 在所有 Java 提交中击败了 56.76% 的用户
   */
  public int maximumScore(int[] nums, int k) {
      int ans = nums[k], n = nums.length;
      int i = k, j = k, min = nums[k];
      while (true) {
          while (i >= 0 && nums[i] >= min) i--;
          while (j < n && nums[j] >= min) j++;
          // (i, j)开区间范围内的最小值为min, 元素数量为 j-i-1
          ans = Math.max(ans, min * (j - i - 1));
          // 降低下一个子数组最小值并扩充边界
          if (i >= 0 && j < n) {
              // 左右两端都可能扩充, 下一个最小值是当前边界值中的较大值
              min = Math.max(nums[i], nums[j]);
          }
          else if (i >= 0) {
              min = nums[i];
          }
          else if (j < n) {
              min = nums[j];
          }
          else {
              break;
          }
      }
      return ans;
  }

标签:好子,nums,1793,indexes,int,数组,ans,leftIdx,LeetCode
From: https://www.cnblogs.com/coding-memory/p/18082556

相关文章

  • 算法沉淀——贪心算法三(leetcode真题剖析)
    算法沉淀——贪心算法三01.买卖股票的最佳时机II02.K次取反后最大化的数组和03.按身高排序04.优势洗牌01.买卖股票的最佳时机II题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/给你一个整数数组prices,其中prices[i]表示某支股票......
  • 代码随想录算法训练营day27 | leetcode 39. 组合总和、40. 组合总和 II、131. 分割回
    目录题目链接:39.组合总和-中等题目链接:40.组合总和II-中等题目链接:131.分割回文串-中等题目链接:39.组合总和-中等题目描述:给你一个无重复元素的整数数组candidates和一个目标整数target,找出candidates中可以使数字和为目标数target的所有不同组合,并以列表形......
  • LeetCode刷题记录——day1
    https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150注:题目有点难理解,多读几遍可以这样考虑,建立另一个临时数组temp,当第i篇文章被引用citiations[i]次时,令j<=citiations[i]的temp[j]均加一,也就是现在对于任意j至少有temp[j]篇论......
  • LeetCode2024年3月18日每日一题(303. 区域和检索 - 数组不可变)
    303.区域和检索-数组不可变一维前缀和定义构建前缀和数组区间求和示例适用场景题目代码解释成员变量构造函数`sumRange`方法注释版代码一维前缀和是处理数组区间求和问题的一种非常有效的方法。它通过预处理输入数组,使得任何区间的和都可以在常数时间内被计算......
  • java数据结构与算法刷题-----LeetCode45. 跳跃游戏 II
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录解题思路:时间复杂度O(n......
  • java数据结构与算法刷题-----LeetCode55. 跳跃游戏
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录解题思路:时间复杂度O(n......
  • leetcode代码记录(二分查找
    目录1.题目:2.我的代码:小结:1.题目:给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且......
  • 【LeetCode 310】最小高度树
    题目描述原题链接:LeetCode.310最小高度树解题思路最小高度树的叶子节点肯定是初始只有一条边的节点;广度优先遍历,逐批将当前叶子节点移除,再将移除后新的叶子节点入队;所有节点全部入队时,当前队列中剩余的最后一批"叶子节点"就是答案;坦白说这题的严格思路证明没想过,第......
  • [Java·算法·中等] LeetCode21. 合并两个有序链表
    人不走空                                          ......
  • 【LeetCode 2684】矩阵中移动的最大次数
    题目描述原题链接:2684矩阵中移动的最大次数解题思路每次只能向右侧的下一列紧挨着的三行严格大的格子移动;能移动到i列代表能移动i次,这取决于i-1列可到达的矩阵位置的状态,即可以整列递推相邻列是否可移动到达;两个方向递推的思路:三个(col+1)位置的状态可以逆推出一个(c......