資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 中的 132 模式
假設我們有一系列 n 個整數 a1, a2, ..., an，132 模式是一個子序列 ai, aj, ak，其中 i < j < k 且 ai < ak < aj。因此，我們必須設計一個演算法，將 n 個數字的列表作為輸入，並檢查列表中是否存在 132 模式。例如，如果輸入類似於 [-1, 3, 2, 0]，則輸出將為 true，因為存在三個模式 [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0]。
為了解決這個問題，我們將遵循以下步驟 -
n := num 的大小，如果 n 為 0，則返回 false
定義一個名為 minVals 的陣列，大小為 n，設定 minVals[0] := num[0]
對於範圍 1 到 n - 1 中的 I
minVals[i] := minVals[i - 1] 和 num[i] 的最小值
建立棧 st
對於範圍 n - 1 到 1 中的 I
minVal := minVals[i - 1]
curr := num[j]
while st 非空且棧頂 <= minVal
從棧 st 中刪除
如果 st 非空且棧頂 < curr，則返回 true
將 num[i] 插入 st
返回 false
示例 (C++)
讓我們看看以下實現以更好地理解它 -
-->
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
if(!n) return false;
vector <int> minVals(n);
minVals[0] = nums[0];
for(int i = 1; i < n; i++){
minVals[i] = min(minVals[i - 1], nums[i]);
}
stack <int> s;
for(int i = n - 1; i > 0; i--){
int minVal = minVals[i - 1];
int curr = nums[i];
while(!s.empty() && s.top() <= minVal) s.pop();
if(!s.empty() && s.top() < curr) return true;
s.push(nums[i]);
}
return false;
}
};
main(){
vector<int> v = {-1,3,2,0};
Solution ob;
cout << (ob.find132pattern(v));
}輸入
[-1,3,2,0]
輸出
1
更新時間：2020 年 4 月 29 日
330 次檢視
廣告