您現在的位置是:首頁 > 棋牌
Java經典演算法:具有上限的子陣列數
- 由 程式設計從Ruandy開始 發表于 棋牌
- 2022-05-26
子陣列是什麼
給定一個由正整陣列成的陣列A,以及兩個正整數L和R(L <= R)。
返回(連續的非空)子陣列的數量,以使該子陣列中最大陣列元素的值至少為L,至多為R。
示例:
輸入:
A = [2,1,4,3]
L = 2
R = 3
輸出:3
說明:有三個滿足要求的子陣列:[2],[2、1],[3]。
Java解決方案
此問題的邊界是每個元素的總和,而不是總和。很容易誤解這個問題,因為有很多與總和有關的問題。
給定樣本[2,1,4,3]中的陣列,我們可以將其轉換為陣列[0,0,1,0],這意味著如果元素在邊界內,則為0。子陣列的數量。
給定一個數組,子陣列的總數遵循以下模式:
[0]-> 1
[0,0]-> 2 + 1(單元素子陣列+ 2元素子陣列)
[0,0,0]-> 3 + 2 + 1
[0,0,0,0]-> 4 + 3 + 2 + 1
因此,解決方案是R的countBelowBoundary-(L-1)的countBelowBoundary。
public
int
numSubarrayBoundedMax(
int
[] A,
int
L,
int
R) {
return
countBelowBoundary(A, R)-countBelowBoundary(A,L-1);}
public
int
countBelowBoundary(
int
[] A,
int
bound){
int
count = 0;
int
temp = 0;
for
(
int
a: A){
if
(a<=bound){
temp = temp +1;
count += temp;
}
else
{
temp = 0;
}
}
return
count;}
時間為O(N),空間為O(1)。
最後,開發這麼多年我也總結了一套學習Java的資料與面試題,如果你在技術上面想提升自己的話,可以關注我,私信傳送領取資料或者在評論區留下自己的聯絡方式,有時間記得幫我點下轉發讓跟多的人看到哦。