刷题day6
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
f[i] = f[i - 1] + f[i - 2];寻找峰值
中等
相关标签
premium lock icon
相关企业
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
这个题没想出来，这里看了下答案，这个答案是真天才。
不过这些题目确实转化一下就有思路了，这里有对称性，因为你这个是峰值，所以沿着峰值是对称的
左边是严格上升，右边是严格下降，所以你只需要找到严格上升的就行了
同时看到logn，一眼就是二分
然后看，如果分成两半，要看的话应该就是严格递增了，如果什么的话，这个峰值在右边呢？
check mid < mid+1 递增的在右边，那右边一定有一个峰值，反之一定在左边
注意这里的二分也不太好想，这里是存在，刚好题目描述这种它是没有平坡的，所以可以这么弄。
感觉非常巧妙
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 wellorbetter's blog！
相关推荐
2026-05-06
刷题day4
插入区间 一眼left right二分+合并区间。然后这个合并区间是只有三个区间。然后我就懒得写区间合并，然后就悲剧了 真神了，为什么要模拟，真的是神了，思路出来0s，模拟1h还不对。真不如区间合并板子用一下。就算我过了，不想改了
2026-05-07
刷题day5
最大正方形 个人思路，0s想出思路，二维前缀和+for nm len 遍历 n^3也能过 这里正解是dp，但是我是感觉这个dp理解起来很费解，感觉很难了。他这个dp ij表示的是边长，因为正方形面积实际上是和边长挂边的，但是边长更简单不用开根号。然后这里你表达的是最大的边长，这里来看的话，我理解你可能会由i-1 j-1 i-j&j-1这三个正方形转化而来110110001比如这个，那就是i-1&j-1011011001 这里就是i-1110110001 这里就是j-1但是实际上能走到扩大的只有111111111因为这三实际上是相互影响的。你如果i-1能扩展到i，那意味着，你这个i-1上面必须至少全部都是1，同理j-1,i-1&j-1要拓展过来，你这部分都得是1那很明显，那就是这三的最小值都得满足满1，然后才能+1那这里dpij >= min(这三个)+1那这里dp ij 能不能不止+1 能+2呢？假设这个最小值是m，然后这个如果dpij >= m+2，那这里就会存在m+2，m+2，这个正方形，它这里面能拆出三个m+1那这...
2026-04-21
刷题day2
移除元素给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。 题意大概意思就是给你一个数组，一个值，返回这个数组去除这个值的顺序数组 解法暴力遍历最简单 然后优化应该就是双指针了。就这样吧，你可以新开一个数组，然后顺序走++，因为你每次++都一定会填入一个你需要的数值然后这个数值的得到是通过原始num数组和val是否相等来的，这个也是顺序++判断的 题解还有个解法没仔细看，叫对撞指针？看不明白就这样吧
2026-04-22
刷题day3
哎，这个合并区间就是咋说呢，左+右对吧？就反正一个左一定要和一个右配对，那就简单了。反正pair排序，按照first排序之后，这个second来看，如果你这个second能比下一个first大，那就能合并，不然就push非常简单的模拟的思路，nlogn 具体写就sort一下begin end，加一个lambda [](&a, &b)然后就开始写区间，这个区间开头是l，r就0那个左右然后就开始更新，如果在区间内，就更新r，这个r就是当前这个两个r的max也就是当前r和这个r的最大值如果不是合并的，那就更新了，同时push一下然后最后剩下一组，就是更新了的最后一组/没更新的合并的，push没问题。 12345678910111213141516171819202122232425262728class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort...
2026-04-20
刷题day1
题目给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。 思路这里要我返回这个顺序递增的这个数组，最暴力就是平移+排序然后我的思路是，你后面这个nums2, 他可以二分找到这个要插入的位置，然后这插入的这个位置是一个顺序set对应每个nums2的元素都需要对nums1来进行二分，如果num1 n, nums2 m,那这里复杂度就是mlogn，然后这里我需要对每个插入的这些nums2的这些元素分别来做排序也就是milogmi, sum mi = m; 每个桶大小 mi，排序 O(mi log mi)，总和 O(Σ mi log mi)，其中 Σmi = m由于 Σ mi log mi ≤ m log m（当所有元素集中在一个桶...
