排列硬币

题目 排列硬币

image-2ba634b1

思路分析

image-136eeb69

初始想法是预处理出每行放满后一共有多少个

找完整行数就是找≤x的最后那个数

后面发现可以直接找mid

通过计算mid * (mid + 1) / 2去与结果比较即可

即把预处理简化成每次找的时候check一次

image-da1a8162

代码实现

class Solution {

public:

    int arrangeCoins(int n) {

        long long l=0,r=n;

        while(l<r)

        {

            long long m=(l+r+1)/2;

            if(m*(m+1)/2<=n)

                l=m;

            else

                r=m-1;

        }

        return r;

    }

};

同类题型

视频讲解

⬅️ 愤怒的牛 🏠 00-刷题理模型 ➡️ 无线网络