資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢列表nums中滿足nums[i] < nums[k] < nums[j]的三元組
假設我們有一個名為nums的數字列表，我們需要檢查是否存在三元組(i, j, k)使得i < j < k並且nums[i] < nums[k] < nums[j]。
因此，如果輸入類似於nums = [2, 12, 1, 4, 4]，則輸出將為True，因為[2, 12, 4]滿足條件，因為2 < 4 < 12。
為了解決這個問題，我們將遵循以下步驟：
n := nums的大小
定義一個大小為n的陣列left
left[0] := nums[0]
for i := 1 to n-1 do −
left[i] := min(nums[i], left[i - 1])
定義一個棧st
for i := n - 1 downto 1 do −
x := left[i - 1]
while st不為空且st的棧頂 <= x do −
從st中彈出元素
if st不為空且x < nums[i]且nums[i] > st的棧頂，則 −
返回true
將nums[i]壓入st
返回false
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& nums) {
int n = nums.size();
vector<int> left(n);
left[0] = nums[0];
for (int i = 1; i < n; i++) {
left[i] = min(nums[i], left[i - 1]);
}
stack<int> st;
for (int i = n - 1; i >= 1; i--) {
int x = left[i - 1];
while (!st.empty() && st.top() <= x)
st.pop();
if (!st.empty() && x < nums[i] && nums[i] > st.top())
return true;
st.push(nums[i]);
}
return false;
}
};
bool solve(vector<int>& nums) {
return (new Solution())->solve(nums);
}
int main(){
vector<int> v = {2, 12, 1, 4, 4};
cout << solve(v);
}輸入
{2, 12, 1, 4, 4}輸出
1
更新於：2020年12月22日
251 次瀏覽
廣告