LeetCode978. 최장 급류 서브 그룹 (동적 기획)
2209 단어 동적 기획
https://leetcode-cn.com/problems/longest-turbulent-subarray/
A의 하위 그룹 A[i], A[i+1],......,A[j]에서 다음 조건을 충족하면 물살 흐름 하위 배열이라고 합니다.
만약 i<=k < j, k가 홀수일 경우 A[k]> A[k+1], 그리고 k가 짝수일 경우 A[k]
：[9,4,2,10,7,8,8,1,9]
：5
：(A[1] > A[2] < A[3] > A[4] < A[5]) ：[4,8,12,16]
：22. 코드 설명
상태 정의:
초기화: 원소가 하나일 때 물살 수조의 길이는 1이다.출력: 두 상태 수조의 모든 원소의 최대 값은 가장 긴 물살 수조의 길이이다.공간 최적화: 공간 최적화: 현재 단계 상태는 전 단계 상태와 관계가 있기 때문에 상태 그룹을 중복 이용할 수 있다.
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
if n < 2:
return n
increase = [1] * n # i ， arr[i - 1] < arr[i]
decrease = [1] * n # i ， arr[i - 1] > arr[i]
res = 1
for i in range(1, n):
if arr[i-1] < arr[i]:
increase[i] = decrease[i-1] + 1
decrease[i] = 1
elif arr[i-1] > arr[i]:
decrease[i] = increase[i-1] + 1
increase[i] = 1
else:
# ==
increase[i] = 1
decrease[i] = 1
res = max(res, max(increase[i], decrease[i]))
return res
arr = [9,4,2,10,7,8,8,1,9]
s = Solution()
print(s.maxTurbulenceSize(arr))https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/zui-chang-tuan-liu-zi-shu-zu-by-leetcode-zqoq/
https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/yi-zhang-dong-tu-xiang-jie-dong-tai-gui-wrwvn/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
