好的子陣列的最大分數 Maximum Score of a Good Subarray_Leetcode#1793

這題的題目在這裡:

題目敘述

好陣列定義是: 有包含nums[k]的子陣列。

分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)

其中， i, j 分別是子陣列的左端點和右端點

請問，好的子陣列的最大分數是多少?

測試範例

Example 1:

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15. 

Example 2:

Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

約束條件

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 2 * 104
• 0 <= k < nums.length

演算法

因為題目一開始要求好的子陣列一定要包含nums[k]

所以讓滑窗初始化在nums[k]

接著，分數的定義是 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)

= 滑窗內的最小值 * 滑窗長度

為了最大化分數，讓滑窗往左右兩個，其中比較大的那一側去延伸，盡量讓分數維持住，下滑的慢一點。每一回合迭代去更新滑窗位的位置 和 分數的最大值。

最後，全部的滑窗延伸走完之後，分數的最大值就是 好的子陣列的最大分數，也是題目所求的最終答案。

程式碼

class Solution:
　def maximumScore(self, nums: List[int], k: int) -> int:

　　# Initialize sliding window at nums[k]
　　left, right = k, k
　　min_val = nums[k]

　　# Max score of good array
　　max_score = min_val
　　
　　while left > 0 or right < len(nums) - 1:

　　　if left == 0 or (right < len(nums) - 1 and nums[right + 1] > nums[left - 1]):
　　　　# right hand side is larger
　　　　right += 1
　　　else:
　　　　# left hand side is larger
　　　　left -= 1

　　　# update minimal value of sliding window
　　　min_val = min(min_val, nums[left], nums[right])

　　　# update and maximize score of good array
　　　max_score = max(max_score, min_val * (right - left + 1))
　　
　　return max_score

複雜度分析

時間複雜度: O( n)
一次線性掃描，滑窗從長度為1 拓展到長度為n。

空間複雜度: O(1)
使用到的變數都是固定尺寸的臨時變數，皆為常數級別O(1)。

關鍵知識點

為了最大化分數，讓滑窗往左右兩個，其中比較大的那一側去延伸，盡量讓分數維持住，下滑的慢一點。每一回合迭代去更新滑窗位的位置 和 分數的最大值。

Reference:

[1] Python O(n) by sliding window and greedy [w/ Comment] - Maximum Score of a Good Subarray - LeetCode