登录
  • #刷题
  • #动态规划

请教大家一道题:wiggle subsequence

yangzhilin
531
1
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条回复
热度排序

发表回复