thảo luận Leetcode mỗi ngày

class Solution {
    public int[] sortArray(int[] nums) {
        Stack<Integer> stk = new Stack<>();
        for (int num : nums) {
            stk.add(num);
        }
        for (int i = 0; i < nums.length; i++) {
            sortStack(stk);
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            nums[i] = stk.pop();
        }

        return nums;
    }

    public void sortStack(Stack<Integer> stk) {
        if (stk.isEmpty()) return;

        int top = stk.pop();
        if (!stk.isEmpty() && top < stk.peek()) {
            int temp = stk.pop();
            stk.add(top);
            top = temp;
        }

        sortStack(stk);

        stk.add(top);
    }
}

class Solution {
    static boolean[] PS = pS(999);

    public static boolean primeSubOperation(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int prev = i > 0 ? nums[i - 1] : 0;
            int p = pClUpTo(nums[i] - prev, PS);
            if (p != -1) nums[i] -= p;
            if (i > 0 && nums[i] <= nums[i - 1]) return false;
        }
        return true;
    }

    public static int pClUpTo(int p, boolean[] sieve) {
        while (p-- > 2) { if (sieve[p]) return p; }
        return p < 2 ? -1 : p;
    }

    public static boolean[] pS(int n) {
        boolean[] rs = new boolean[(int) (n + 1)];
        if (n >= 2) rs[2] = true;
        for (int i = 3; i <= n; i += 2) rs[i] = true;
        for (int i = 3, end = (int) Math.sqrt(n); i <= end; i += 2) {
            if (rs[i]) for (int j = i * i; j <= n; j += i << 1) rs[j] = false;
        }
        return rs;
    }
}

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items = sorted(items)
        for i in range(1, len(items)):
            items[i][1] = max(items[i][1], items[i - 1][1])
        
        def bisect(target):
            left = 0
            right = len(items) - 1
            while left <= right:
                mid = left + (right - left)//2
                if target >= items[mid][0]:
                    left = mid + 1
                else:
                    right = mid - 1
            if left == 0:
                return 0
            return items[left - 1][1]
                
        return [ bisect(query) for query in queries ]

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        map<int, int> beauty;
        vector<int> newItems;
        int n = items.size();

        for (int i = 0; i < n; i++) {
            if (beauty[items[i][0]] == 0) {
                beauty[items[i][0]] = items[i][1];
                newItems.push_back(items[i][0]);
            }
            else {
                beauty[items[i][0]] = max(beauty[items[i][0]], items[i][1]);
            }
        }

        sort(newItems.begin(), newItems.end());

        int maxBeautySoFar = 0;
        for (int price : newItems) {
            maxBeautySoFar = max(maxBeautySoFar, beauty[price]);
            beauty[price] = maxBeautySoFar;
        }

        vector<int> ans;

        for (int i = 0; i < queries.size(); i++) {
            int key = binarySearch(newItems, queries[i]);
            if (key >= 0) { 
                ans.push_back(beauty[newItems[key]]);
            } else {
                ans.push_back(0);
            }
        }

        return ans;
    }

    int binarySearch(vector<int>& newItems, int target) {
        int left = 0;
        int right = newItems.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int value = newItems[mid];

            if (value == target) return mid;
            else if (value > target) right = mid - 1;
            else if (value < target) left = mid + 1;
        }

        return right; 
    }
};

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        map<int, int> m;
        for (auto& p : items) {
            if (m.count(p[0]) == 0 || m[p[0]] < p[1])
                m[p[0]] = p[1];
        }
        int maxBeauty = 0;
        for (auto& p : m) {
            if (p.second < maxBeauty)
                p.second = maxBeauty;
            else if (maxBeauty < p.second)
                maxBeauty = p.second;
        }

        vector<int> ans;
        ans.reserve(queries.size());
        for (auto& q : queries) {
            auto lb = m.upper_bound(q);
            if (lb == m.begin())
                ans.push_back(0);
            else {
                lb--;
                ans.push_back(lb->second);
            }
        }
        return ans;
    }
};

function maximumBeauty(items: number[][], q: number[]): number[] {
    items.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
    
    const maxList: number[][] = [];
    let curMax = 0;
    for (const [u, v] of items) {
        curMax = Math.max(curMax, v);
        maxList.push([u, curMax]);
    }
    const res: number[] = [];
    for (const p of q) {
        let l = 0, r = maxList.length - 1, cur = 0;
        while (l <= r) {
            const m = l + Math.floor((r - l) / 2);
            if (maxList[m][0] <= p) {
                cur = maxList[m][1];
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        res.push(cur);
    }

    return res;
}

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        int n = queries.length;
        int[] res = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(queries[i], k -> new ArrayList());
            map.get(queries[i]).add(i);
        }
        Arrays.sort(queries);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int[] item : items) {
            pq.add(item);
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            int query = queries[i];
            while (!pq.isEmpty() && pq.peek()[0] <= query) {
                max = Math.max(max, pq.poll()[1]);
            }
            for (int index : map.get(query)) {
                res[index] = max;
            }
        }
        return res;
    }
}