［抄題］：

Given an integer array, you need to find one?continuous subarray?that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the?shortest?such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

?[暴力解法]：

時間分析：

空間分析：

?[優(yōu)化后]：

時間分析：

空間分析：

［奇葩輸出條件］：

題目有歧義：其實沒有“最短”的概念，找到一個范圍就行了

［奇葩corner case］：

1234，輸出0。因此i小j大的初始值是-1,0。別的地方不知道能否試試？

［思維問題］：

指針對撞一直走，但是沒想到最后會ij顛倒大小。

［一句話思路］：

i小j大變成了i大j小，所以結(jié)果是i - j + 1

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

不可能i j,l r兩對指針同時走的，一對就夠了

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結(jié)果]：

［總結(jié)］：

指針對撞一直走，但是沒想到最后會ij顛倒大小。i - j + 1

［復雜度］：Time complexity: O(n) Space complexity: O(1)

［英文數(shù)據(jù)結(jié)構(gòu)或算法，為什么不用別的數(shù)據(jù)結(jié)構(gòu)或算法］：

［關鍵模板化代碼］：

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

?[代碼風格] ：

class Solution {public int findUnsortedSubarray(int[] nums) {//ccif (nums == null || nums.length == 0) {return 0;}//ini: l rint min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, i = -1, j = 0;//for loopfor (int l = 0, r = nums.length - 1; r >= 0; l++, r--) {max = Math.max(nums[l], max);if (nums[l] != max) {i = l;}min = Math.min(nums[r], min);if (nums[r] != min) {j = r;}}return i - j + 1;} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/immiao0319/p/8905772.html

總結(jié)

以上是生活随笔為你收集整理的581. Shortest Unsorted Continuous Subarray连续数组中的递增异常情况的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。