[LeetCode] 581、最短無序連續子數組

題目描述

給定一個整數數組，你需要尋找一個連續的子數組，如果對這個子數組進行升序排序，那麼整個數組都會變為升序排序（

<=

）。你找到的子數組應是最短的，請輸出它的長度。（可能有重複元素）

示例：

輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你隻需要對 [6, 4, 8, 10, 9] 進行升序排序，那麼整個表都會變為升序排序。
           

解題思路

做出來容易，優化不容易。

• 簡單思路，排序：我們将數組

  nums

  進行排序，記為

  nums_sorted

  。然後我們比較

  nums

  和

  nums_sorted

  的元素來決定最左邊和最右邊不比對的元素。它們之間的子數組就是要求的最短無序子數組。 O ( n l o g n ) + O ( n ) O(nlogn) + O(n) O(nlogn)+O(n)
• 兩次周遊：從前往後，記錄下周遊過的值裡面的最大值；從後往前周遊，記錄下周遊過的值裡面的最小值。
  • 從前往後：如果

    nums[i] < tmpMax

    ，就将右邊界更新為

    i

    ，否則更新

    tmpMax

    。
  • 從後往前：如果

    nums[i] > tmpMin

    ，就将左邊界更新為

    i

    ，否則更新

    tmpMin

    。
  最終：

  return right - left + 1 > 0? right - left + 1: 0;

參考代碼

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int length = nums.size();
        if(length <= 1)
            return 0;
        
        int right = 0, left = length - 1;
        int tmpMax = INT_MIN, tmpMin = INT_MAX;
        for(int i = 0; i < length; i++){
            if(nums[i] < tmpMax)
                right = i;
            else
                tmpMax = nums[i];
        }
        for(int i = length-1; i >= 0; i--){
            if(nums[i] > tmpMin)
                left = i;
            else
                tmpMin = nums[i];
        }
        
        return right - left + 1 > 0? right - left + 1: 0;
    }
};