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


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