2017. Grid Game - Medium

前往題目

思路

1. 計算第一列與第二列每一格的prefix sum
2. 疊代一列
3. 每一格都算出當前如果待在top可以拿到多少points，下去bottom可以拿到多少points
4. robot2取top和bottom比較大的那個
5. 結果是每次循環都盡可能取更小的robot2分數

Code

Java版本

class Solution {
    public long gridGame(int[][] grid) {
        // Use long to prevent sum up overflow
        long[] prefix_top = new long[grid[0].length];
        long[] prefix_bottom = new long[grid[0].length];
        
        // Copy top row and bottom row
        for(int i = 0; i < grid[0].length; ++i)
        {
            prefix_top[i] = grid[0][i];
            prefix_bottom[i] = grid[1][i];
        }

        // Calculate prefix sum
        for (int i = 1; i < grid[0].length; ++i) {
            prefix_top[i] += prefix_top[i - 1];
            prefix_bottom[i] += prefix_bottom[i - 1];
        }

        long res = Long.MAX_VALUE;
        long robot2 = Long.MIN_VALUE;

        // Go through the grid, find the optimal
        for (int i = 0; i < grid[0].length; ++i) {
            // Stays on top or bottom
            // chose by robot1, robot2 only has the remaining
            long top = prefix_top[grid[0].length - 1] - prefix_top[i];
            long bottom = 0;
            
            // In case out of bound
            if (i > 0) {
                bottom = prefix_bottom[i - 1];
            }

            // Robot2 tries to get as many points as possible
            robot2 = Math.max(top, bottom);
            // Obtain robot2's lowest points
            res = Math.min(res, robot2);
        }

        return res;
    }
}