資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++ 中帶邊界最大值的子陣列個數
假設我們有一個包含正整數的陣列 A，並且還給定了兩個正整數 L 和 R。我們需要找到這樣的（連續的、非空的）子陣列的數量，使得該子陣列中最大陣列元素的值至少為 L 且至多為 R。因此，如果 A = [2,1,4,3] 且 L = 2 且 R = 3，則輸出將為 3，因為有三個子陣列滿足要求。這些子陣列是 [2]、[2,1]、[3]。
為了解決這個問題，我們將遵循以下步驟：
ret := 0，dp := 0，prev := -1
for i in range 0 to size of A – 1
if A[i] < L and i > 0, then ret := ret + dp
if A[i] > R, then prev := i and dp := 0
否則，當 A[i] >= L and A[i] <= R 時，則 dp := i – prev and ret := ret + dp
return ret
示例（C++）
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
int ret = 0;
int dp = 0;
int prev = -1;
for(int i = 0; i < A.size(); i++){
if(A[i] < L && i > 0){
ret += dp;
}
if(A[i] > R){
prev = i;
dp = 0;
}
else if(A[i] >= L && A[i] <= R){
dp = i - prev;
ret += dp;
}
}
return ret;
}
};
main(){
vector<int> v = {2,1,4,3};
Solution ob;
cout << (ob.numSubarrayBoundedMax(v, 2, 3));
}輸入
[2,1,4,3] 2 3
輸出
3
更新於: 2020年5月2日
162 次檢視
廣告