Question

1618. 找出适应屏幕的最大字号

English Version

题目描述

给定一个字符串 text。并能够在 宽为 w 高为 h 的屏幕上显示该文本。

字体数组中包含按升序排列的可用字号，您可以从该数组中选择任何字体大小。

您可以使用FontInfo接口来获取任何可用字体大小的任何字符的宽度和高度。

FontInfo接口定义如下：

interface FontInfo {
  // 返回 fontSize 大小的字符 ch 在屏幕上的宽度。
  // 每调用该函数复杂度为 O(1)
  public int getWidth(int fontSize, char ch);

  // 返回 fontSize 大小的任意字符在屏幕上的高度。
  // 每调用该函数复杂度为 O(1)
  public int getHeight(int fontSize);
}

一串字符的文本宽度应该是 每一个字符 在对应字号(fontSize)下返回的宽度getWidth(fontSize, text[i])的 总和 。对应字号的文本高度可由 getHeight(fontSize) 计算得到。

请注意：文本最多只能排放一排

如果使用相同的参数调用 getHeight 或 getWidth ，则可以保证 FontInfo 将返回相同的值。

同时，对于任何字体大小的 fontSize 和任何字符 ch ：

• getHeight(fontSize) <= getHeight(fontSize+1)
• getWidth(fontSize, ch) <= getWidth(fontSize+1, ch)

返回可用于在屏幕上显示文本的最大字体大小。如果文本不能以任何字体大小显示，则返回-1。

示例 1:

输入: text = "helloworld", w = 80, h = 20, fonts = [6,8,10,12,14,16,18,24,36]
输出: 6

示例 2：

输入: text = "leetcode", w = 1000, h = 50, fonts = [1,2,4]
输出: 4

示例 3：

输入: text = "easyquestion", w = 100, h = 100, fonts = [10,15,20,25]
输出: -1

 

注意:

• 1 <= text.length <= 50000
• text 只包含小写字母
• 1 <= w <= 107
• 1 <= h <= 104
• 1 <= fonts.length <= 105
• 1 <= fonts[i] <= 105
• fonts 已经按升序排序，且不包含重复项。

解法

方法一：二分查找

根据题目描述，字体数组按升序排列。因此，我们可以二分枚举字体大小 fontSize，找到最大的并且能够在屏幕上显示文本字体大小即可。

时间复杂度 $O(m\log n)$。其中 $m$, $n$ 为文本 text 的长度以及字体大小 fonts 个数。

关于二分查找，见整数二分算法模板 2。

# """
# This is FontInfo's API interface.
# You should not implement it, or speculate about its implementation
# """
# class FontInfo(object):
#  Return the width of char ch when fontSize is used.
#  def getWidth(self, fontSize, ch):
#    """
#    :type fontSize: int
#    :type ch: char
#    :rtype int
#    """
#
#  def getHeight(self, fontSize):
#    """
#    :type fontSize: int
#    :rtype int
#    """
class Solution:
  def maxFont(
    self, text: str, w: int, h: int, fonts: List[int], fontInfo: 'FontInfo'
  ) -> int:
    def check(size):
      if fontInfo.getHeight(size) > h:
        return False
      return sum(fontInfo.getWidth(size, c) for c in text) <= w

    left, right = 0, len(fonts) - 1
    ans = -1
    while left < right:
      mid = (left + right + 1) >> 1
      if check(fonts[mid]):
        left = mid
      else:
        right = mid - 1
    return fonts[left] if check(fonts[left]) else -1

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface FontInfo {
 *   // Return the width of char ch when fontSize is used.
 *   public int getWidth(int fontSize, char ch) {}
 *   // Return Height of any char when fontSize is used.
 *   public int getHeight(int fontSize)
 * }
 */
class Solution {
  public int maxFont(String text, int w, int h, int[] fonts, FontInfo fontInfo) {
    int left = 0, right = fonts.length - 1;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (check(text, fonts[mid], w, h, fontInfo)) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
  }

  private boolean check(String text, int size, int w, int h, FontInfo fontInfo) {
    if (fontInfo.getHeight(size) > h) {
      return false;
    }
    int width = 0;
    for (char c : text.toCharArray()) {
      width += fontInfo.getWidth(size, c);
    }
    return width <= w;
  }
}

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * class FontInfo {
 *   public:
 *   // Return the width of char ch when fontSize is used.
 *   int getWidth(int fontSize, char ch);
 *
 *   // Return Height of any char when fontSize is used.
 *   int getHeight(int fontSize)
 * };
 */
class Solution {
public:
  int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
    auto check = [&](int size) {
      if (fontInfo.getHeight(size) > h) return false;
      int width = 0;
      for (char& c : text) {
        width += fontInfo.getWidth(size, c);
      }
      return width <= w;
    };
    int left = 0, right = fonts.size() - 1;
    while (left < right) {
      int mid = (left + right + 1) >> 1;
      if (check(fonts[mid])) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return check(fonts[left]) ? fonts[left] : -1;
  }
};

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * function FontInfo() {
 *
 *    @param {number} fontSize
 *    @param {char} ch
 *     @return {number}
 *     this.getWidth = function(fontSize, ch) {
 *      ...
 *     };
 *
 *    @param {number} fontSize
 *     @return {number}
 *     this.getHeight = function(fontSize) {
 *      ...
 *     };
 * };
 */
/**
 * @param {string} text
 * @param {number} w
 * @param {number} h
 * @param {number[]} fonts
 * @param {FontInfo} fontInfo
 * @return {number}
 */
var maxFont = function (text, w, h, fonts, fontInfo) {
  const check = function (size) {
    if (fontInfo.getHeight(size) > h) {
      return false;
    }
    let width = 0;
    for (const c of text) {
      width += fontInfo.getWidth(size, c);
    }
    return width <= w;
  };
  let left = 0;
  let right = fonts.length - 1;
  while (left < right) {
    const mid = (left + right + 1) >> 1;
    if (check(fonts[mid])) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  return check(fonts[left]) ? fonts[left] : -1;
};