資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++ 中分割列表
假設我們有一個名為 nums 的整數列表，我們需要確定是否可以將列表劃分為兩個子列表（非空），使得左側部分中的每個數字都嚴格小於右側部分中的每個數字。
因此，如果輸入類似於 [6,4,3,8,10]，則輸出將為 true，因為 left = [6,4,3] 且 right = [8,10]
為了解決這個問題，我們將遵循以下步驟：
n := nums 的大小
定義一個大小為 n 的陣列 right
定義一個大小為 n 的陣列 left
left[0] := nums[0]
right 的最後一個元素 := nums 的最後一個元素
對於初始化 i := 1，當 i < n 時，更新（將 i 增加 1），執行：
left[i] := left[i - 1] 和 nums[i] 的最大值
對於初始化 i := n - 2，當 i >= 0 時，更新（將 i 減小 1），執行：
right[i] := right[i + 1] 和 nums[i] 的最小值
對於初始化 i := 0，當 i < n - 1 時，更新（將 i 增加 1），執行：
如果 left[i] < right[i + 1]，則：
返回 true
返回 false
讓我們檢視以下實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int> &nums) {
int n = nums.size();
vector<int> right(n);
vector<int> left(n);
left[0] = nums[0];
right.back() = nums.back();
for (int i = 1; i < n; i++) {
left[i] = max(left[i - 1], nums[i]);
}
for (int i = n - 2; i >= 0; i--) {
right[i] = min(right[i + 1], nums[i]);
}
for (int i = 0; i < n - 1; i++) {
if (left[i] < right[i + 1])
return true;
}
return false;
}
};
main() {
Solution ob;
vector<int> v = {6,4,3,8,10};
cout << (ob.solve(v));
}輸入
{6,4,3,8,10}輸出
1
更新於： 2020年9月2日
892 次檢視
廣告