注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
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[i] > nums[i-1]
2. down position, it means nums[i] < nums[i-1]
3. equals to position, nums[i] == nums[i-1]
The updates are done as:
If nums[i] > nums[i-1], that means it wiggles up. The element before it must be a down position. So up[i] = down[i-1] + 1, down[i] remains the same as down[i-1]. If nums[i] < nums[i-1], that means it wiggles down. The element before it must be a up position. So down[i] = up[i-1] + 1, up[i] remains the same as up[i-1]. If nums[i] == nums[i-1], that means it will not change anything becaue it didn't wiggle at all. So both down[i] and up[i] remain the same as down[i-1] and up[i−1]. 我不明白的为什么1只比较了nums[i] > nums[i-1], 难道说nums[i]一定要连接上nums[i-1]咯?可是不一定呀,比方说有可能一个数组中有连续递增的几个数,nums[i]和nums[i-2]连起来也可以呀。我看了网上其他解释也没有讲这一点。
|