LeetCode581:最短无序连续子数组（贪心算法解析）

LeetCode 581: 最短无序连续子数组（贪心算法解析）

• 贪心算法简介
• 解题步骤
• 算法实现

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最优的算法。这种算法并不总是能够找到全局最优解，但适用于某些特定问题。贪心算法的关键在于选择性质和无后效性。

选择性质指的是可以通过局部最优选择来达到全局最优。无后效性则意味着已经做出的选择不会影响未来的选择，即每一个状态都是独立的。

1. 建立数学模型来描述问题。

2. 将问题分解为若干个子问题。

3. 对每个子问题求解，获得局部最优解。

4. 将这些局部最优解组合成原问题的解。

给定一个整数数组 nums，找出一个最短的连续子数组，使得将这个子数组排序后，整个数组变为升序排序。返回这个子数组的长度。

例如：

示例 1: 输入: nums = [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个数组都会变为升序排序。

示例 2: 输入: nums = [1, 2, 3, 4] 输出: 0 示例 3: 输入: nums = [1] 输出: 0

通过对原数组进行排序，然后与原数组进行比较，找出第一个和最后一个不同的元素位置，这两个位置之间的子数组即为需要排序的最短子数组。

图示:

// 整体思路是对数组排序，找出序列不正常的起始位置和最后位置并返回 var findUnsortedSubarray = function(nums) { let num = []; for (let k = 0; k a - b); let i = 0; let j = nums.length; while (num[i] == nums[i] && i = 0) { j--; } if (i == nums.length && j == -1) return 0; return j - i + 1; }

通过维护当前的最大值和最小值，如果在最大值的右边有比它小的数，则记录该位置；如果在最小值的左边有比它大的数，同样记录该位置。最终得到的两个位置即为无序子数组的起始和结束位置。

起始位置演示:

结束位置演示:

// 题目要求，如果是升序排列，那么左边的数据比右边的数据小 var findUnsortedSubarray = function(nums) { let len = nums.length; let l = -1; let r = -1; let max = nums[0]; let min = nums[len - 1]; for (let i = 0; i = max) { max = nums[i]; } else { r = i; } } for (let j = len - 1; j >= 0; j--) { if (nums[j] <= min) { min = nums[j]; } else { l = j; } } if (r == -1 && l == -1) return 0; return r - l + 1; }