1403. Minimum Subsequence in Non-Increasing Order¶

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public: vector minSubsequence(vector& nums) { vector ans; priority_queue maxHeap(nums.begin(), nums.end()); int half = accumulate(nums.begin(), nums.end(), 0) / 2; while (half >= 0) { ans.push_back(maxHeap.top()); half -= maxHeap.top(), maxHeap.pop(); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public List minSubsequence(int[] nums) { List ans = new ArrayList<>(); Queue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (final int num : nums) maxHeap.offer(num); int half = Arrays.stream(nums).sum() / 2; while (half >= 0) { ans.add(maxHeap.peek()); half -= maxHeap.poll(); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def minSubsequence(self, nums: List[int]) -> List[int]: ans = [] maxHeap = [-num for num in nums] heapq.heapify(maxHeap) half = sum(nums) // 2 while half >= 0: ans.append(-maxHeap[0]) half += heapq.heappop(maxHeap) return ans