題目地址:

https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/

題目描述

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,1,4,3], left = 2, right = 3

Output: 3

Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Example 2:

Input: nums = [2,9,2,5,6], left = 2, right = 8

Output: 7

題目大概就是要求一個數(shù)組的子數(shù)組中最大值滿足在范圍[left, right]的個數(shù)。

雖然難度為中等， 但是這題有很多種方法解決，于是寫篇博客隨便復習一下。

思路1: 動態(tài)規(guī)劃

我們先來證明這個問題是具有子結(jié)構(gòu)的，也就是說我們可以從解決子問題開始最終能得出我們的答案。

我們先來定義子問題，要求數(shù)組最終的子數(shù)組滿足的個數(shù), 我們可以定義 i 表示以 i 作為最后元素中子數(shù)組的個數(shù), 于是我們就拆解出了 i 個子問題, 假設(shè)這 i 個子問題的解為

那么根據(jù)題意問題的答案為? , 即每個以 i 結(jié)尾的子數(shù)組的個數(shù)的和。由子數(shù)組的性質(zhì)可知，每個子問題都是唯一的， 遞歸地,?也是唯一的，于是我們證明了可以從子問題中推出原問題的解，這個問題是具有子結(jié)構(gòu)的。

一個問題證明了具有子結(jié)構(gòu)后，我們就可以通過遞歸或遞推(動態(tài)規(guī)劃)來解決了，我們先假設(shè)出狀態(tài):

dp[i][0] : 以 i 作為最后元素中子數(shù)組的最大值小于在 [left, right] 中的個數(shù)

dp[i][1] : 以 i 作為最后元素中子數(shù)組的最大值在 [left, right] 中的個數(shù)

已知 nums 里面的元素會出現(xiàn)三種情況:

當 nums[i] >= left 且 nums <= right :??此時 nums[i] 一定會出現(xiàn)在符合的子數(shù)組中, 由于符合的子數(shù)組中滿足 nums[i] 為最大值即可, 那么還可能出現(xiàn)比 nums[i] 小的元素, 并且要求是連續(xù)的，所有該子問題的解可以轉(zhuǎn)化為 i - 1 (上一個)狀態(tài)的解:

我們此時的狀態(tài)方程可以這樣寫:

? ? ? ? ? ? ??dp[i][1] = 1 + dp[i - 1][1] + dp[i - 1][0]

當 nums[i] < left : dp[i][0] = dp[i - 1][0] + 1

????????????????????????????dp[i][1] = dp[i - 1][1]

當 nums[i] > right 時: 這個元素對我們的答案沒有如何貢獻, 此時dp[i][0] = dp[i][1] = 0

注意到每個狀態(tài)只與上一個狀態(tài)有關(guān)，我們還可以用滑動數(shù)組進行優(yōu)化(這里就不寫惹。。。)

思路2: 單調(diào)棧

對于數(shù)組里面的每一個元素 nums[i], 我們考慮它對答案的貢獻。如果這個 nums[i] 在 [left, right] 范圍內(nèi)， 我們定義 l[i] 為 nums[i] 左邊第一個大于 nums[i] 的元素的下標, r[i] 為 nums[i] 右邊第一個大于 nums[i] 的元素的下標, 那么已nums[i]為最大值的子數(shù)組有 (i - l[i]) * (r[i] - i) 個(相當于組合問題吧。。。)， 那么我們對每個?(i - l[i]) * (r[i] - i)?? 求和就是答案了。

其中 l[i] 和 r[i] 可以通過 單調(diào)棧 這種數(shù)據(jù)結(jié)構(gòu)來計算出來。時間復雜度僅為 O(n)。

思路3: 模擬 + 計數(shù)

利用前綴和的思想，我們先計算出 x = 最大值為?right 的子數(shù)組的個數(shù), y = 最大值為 left - 1 的子數(shù)組的個數(shù), 然后 x - y 就是 最大值范圍在 [left, right]的子數(shù)組的個數(shù)了!