แยกรายการใน C++

สมมติว่าเรามีรายการจำนวนเต็มที่เรียกว่า nums เราต้องค้นหาว่าเราสามารถแบ่งรายการออกเป็นสองรายการย่อย (ไม่ว่าง) ได้หรือไม่ โดยที่ตัวเลขในส่วนด้านซ้ายจะน้อยกว่าอย่างเคร่งครัด กว่าทุกเลขในส่วนที่ถูกต้อง

ดังนั้น หากอินพุตเป็นเหมือน [6,4,3,8,10] ผลลัพธ์จะเป็นจริง เช่น ซ้าย =[6,4,3] และขวา =[8,10]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

n :=ขนาดของ nums
กำหนดขนาดอาร์เรย์ด้านขวา n
กำหนดอาร์เรย์ด้านซ้ายของขนาด n
ซ้าย[0] :=nums[0]
องค์ประกอบสุดท้ายทางขวา :=องค์ประกอบสุดท้ายของ nums
สำหรับการเริ่มต้น 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
- ถ้า left[i]
  - คืนความจริง
คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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}