[LeetCode][Python3] 581. Shortest Unsorted Continuous Subarray

Problem :

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/

My Solution :

class Solution:

def findUnsortedSubarray(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

i, j = 0, len(nums)-1

while i < j:

if nums[i] > nums[i+1]:

break

i += 1

if i == j:

return 0

while i < j:

if nums[j] < nums[j-1]:

break

j -= 1

m = min(nums[i:j+1])

M = max(nums[i:j+1])

while -1 < i and nums[i] > m:

i -= 1

while j < len(nums) and nums[j] < M:

j += 1

return j - i - 1

Comment :

지난번 풀었던 다른 문제와 비슷한 느낌이 들어서 비슷하게 접근해 보았다.

2018/09/13 - [프로그래밍] - [LeetCode][Python3] 665. Non-decreasing Array

나의 전략은 이렇다. 왼쪽 경계를 정렬이 깨지는 곳 까지 오른쪽으로 옮기고, 오른쪽 경계를 정렬이 깨지는 곳 까지 왼쪽으로 옮긴 다음, 가운데 영역에서 최대, 최소 값을 구한다. 그리고 왼쪽 경계는 최소값 이하를 만날 때 까지 다시 왼쪽으로 옮기고, 오른쪽 경계는 최대값 이상을 만날 때 까지 다시 오른쪽으로 옮긴다. 그러면 둘 사이 구간이 재정렬이 필요한 구간이 된다.