- #刷题
- #动态规划
请教大家一道题:wiggle subsequence

5311
376. Wiggle Subsequence 这道题是dynamic programming的题。我看了官方的解法,一和二都懂了,但是对于第三种线性时间的解法存在疑惑。
这个解法核心是这样的:
这个解法核心是这样的:
Any element in the array could correspond to only one of the three possible states:
1. up position, it means nums > nums[i-1]
2. down position, it means nums < nums[i-1]
3. equals to position, nums == nums[i-1]
The updates are done as:
If nums > nums[i-1], that means it wiggles up. The element before it must be a down position. So up = down[i-1] + 1, down remains the same as down[i-1]. If nums < nums[i-1], that means it wiggles down. The element before it must be a up position. So down = up[i-1] + 1, up remains the same as up[i-1]. If nums == nums[i-1], that means it will not change anything becaue it didn't wiggle at all. So both down and up remain the same as down[i-1] and up[i−1].我不明白的为什么1只比较了nums > nums[i-1], 难道说nums一定要连接上nums[i-1]咯?可是不一定呀,比方说有可能一个数组中有连续递增的几个数,nums和nums[i-2]连起来也可以呀。我看了网上其他解释也没有讲这一点。
1条回复
热度排序