You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.
class Solution { public int arrangeCoins(int n) { int res = 0; int le = n; for(int i = 1; i <= n; i++){ if(le < i) return i-1; else{ le -= i; } } return n; } }
或者二分法
class Solution { public int arrangeCoins(int n) { long left = 0, right = n; long k, curr; while (left <= right) { k = left + (right - left) / 2; System.out.println(k); curr = k * (k + 1) / 2; if (curr == n) return (int)k; if (n < curr) { right = k - 1; } else { left = k + 1; } } return (int)right; } }
Find the maximum kk such that k (k + 1)/2\≤N.
原文：https://www.cnblogs.com/wentiliangkaihua/p/13222144.html