LeetCode(微博搜索)-20240124-1

本条微博地址 __MIC2OSofT__
请网友监督我明天开始刷leetcode[桃里桃气] 本条微博地址 gitpush-force
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
单调栈。分别从左到右和从右向左遍历，维护单调栈，得出以i位置为山峰时，山峰两侧高度之和。计算时有若存在第一个j位置高度小于等于i位置高度，有sum[i]=sum[j]+height[i] * abs(i – j)。根据上述式子，寻找全局最优值即可。注意数组越界和数字溢出问题。这道题数据量1e3也可以直接暴力模拟山脉求解。
国际站每日一题今日思路：
dfs问题。从根节点向叶子节点进行遍历，可以使用数组或者一个整型维护数字出现频率，遍历到叶子节点时判断至多有一个数字出现频率为奇数。对于喜欢研究性能的同学，这道题是一个很好的例子。代码写完后会发现虽然大家代码时间复杂度都是O(n),n为节点数，但是性能天壤之别，有的能跑上千毫秒，有的只有200，为什么呢？感兴趣的同学可以试着把发现打在评论区。
#每日一题# #LeetCode# #每天59秒拿下每日一题# 本条微博地址 如果我是管人你会给我上舰吗